#!/usr/bin/env python3
import sys
import re
import collections

START = 'start'
END = 'end'

def dive(nodes, edges, i, visited = [], paths = [], source = None):
    print(f'dive {i} with nodes {nodes} and visited {visited} ({hex(id(visited))})')
    for node in nodes:
        newly_visited = copy.deepcopy(visited)
        if node.islower() and node in visited:
            continue
        newly_visited.append(node)
        if node == END:
            visited.append(node)
            paths.append(visited)
            print(i, paths)
            continue
        dive(edges[node], edges, i + 1, newly_visited, paths, node)
    return paths

def dive3(path, edges, i, paths = []):
    print(f'at {i} with {path}')
    for target in edges[path[-1]]:
        if target.islower() and target in path:
            print(f'nope {path}')
            continue
        path.append(target)
        if target == END:
            print(f'end {path}')
            return [path]
        paths += dive3(path.copy(), edges, i + 1)
    print(paths)
    return paths

def dive2(nodes, edges, i, deque, source = None):
    print(f'dive {i} with nodes {nodes} and visited {visited} ({hex(id(visited))})')
    while len(deque) > 0:
        node, visits = deque.popleft()
        for target in [ n for n in edges[node] if not (n.islower() and n in visits) ]:
            deque.append([target, visits])
        deque.append([node, visits])

edges = {}
for line in sys.stdin:
    a, b = [ group for group in re.match(r'^([a-zA-Z]+)-([a-zA-Z]+)$', line).groups() ]
    if not a in edges: edges[a] = [b]
    else:              edges[a].append(b)
    # undirected graph
    if not b in edges: edges[b] = [a]
    else:              edges[b].append(a)
print(edges)

nodes = [START]
#paths = dive(nodes, copy.deepcopy(edges), 0)
paths = dive3(nodes, edges, 0)
#print(f'{len(paths)} paths:')
#print('\n'.join([str(','.join([ str(node) for node in path ])) for path in paths]))